# -*- coding: utf-8 -*-

def bubble_sort(arr):
    """
    冒泡排序算法
    时间复杂度: O(n²)
    空间复杂度: O(1)
    
    Args:
        arr: 需要排序的列表
        
    Returns:
        排序后的列表
    """
    n = len(arr)
    
    # 遍历所有数组元素
    for i in range(n):
        # 标记此轮是否发生交换
        swapped = False
        
        # 最后i个元素已经在正确位置
        for j in range(0, n - i - 1):
            # 如果当前元素大于下一个元素，则交换它们
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 如果没有发生交换，说明数组已经排序完成
        if not swapped:
            break
    
    return arr


def bubble_sort_optimized(arr):
    """
    优化版冒泡排序算法
    添加了边界优化，记录最后一次交换的位置
    
    Args:
        arr: 需要排序的列表
        
    Returns:
        排序后的列表
    """
    n = len(arr)
    last_exchange = n - 1  # 记录最后一次交换的位置
    
    for i in range(n):
        swapped = False
        current_exchange = 0  # 当前轮次最后一次交换的位置
        
        for j in range(last_exchange):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                current_exchange = j
        
        last_exchange = current_exchange
        
        if not swapped:
            break
    
    return arr


def print_array(arr, title="数组"):
    """打印数组的辅助函数"""
    print("{}: {}".format(title, arr))


if __name__ == "__main__":
    # 测试用例
    test_cases = [
        [64, 34, 25, 12, 22, 11, 90],
        [5, 2, 4, 6, 1, 3],
        [1],
        [],
        [3, 3, 3, 3],
        [9, 8, 7, 6, 5, 4, 3, 2, 1]
    ]
    
    print("=== 冒泡排序算法演示 ===\n")
    
    for i, test_arr in enumerate(test_cases, 1):
        print("测试用例 {}:".format(i))
        print_array(test_arr, "原始数组")
        
        # 创建副本进行排序
        arr_copy = test_arr[:]
        sorted_arr = bubble_sort(arr_copy)
        print_array(sorted_arr, "排序后数组")
        
        print("-" * 40)
    
    print("\n=== 性能对比 ===")
    import time
    import random
    
    # 生成大数组进行性能测试
    large_arr = [random.randint(1, 1000) for _ in range(1000)]
    
    # 测试标准冒泡排序
    start_time = time.time()
    bubble_sort(large_arr[:])
    standard_time = time.time() - start_time
    
    # 测试优化版冒泡排序
    start_time = time.time()
    bubble_sort_optimized(large_arr[:])
    optimized_time = time.time() - start_time
    
    print("标准冒泡排序耗时: {:.4f} 秒".format(standard_time))
    print("优化版冒泡排序耗时: {:.4f} 秒".format(optimized_time))
    print("性能提升: {:.2f}%".format((standard_time - optimized_time) / standard_time * 100)) 